package com.company.algo.DP.subseqProblem.editDistance;

/**392.判断⼦序列
 给定字符串 s 和 t ，判断 s 是否为 t 的⼦序列。
 字符串的⼀个⼦序列是原始字符串删除⼀些（也可以不删除）字符⽽不改变剩余字符相对位置形成的新字符串。
 （例如，"ace"是"abcde"的⼀个⼦序列，⽽"aec"不是）。
 解法1：双指针
 解法2：动态规划
 先将问题转化为求s,t的最长公共子序列，若该公共子序列长度==s.length()，说明s是t的子序列
 dp[i][j]: s[0:i]与t[0:j]的公共子序列长度
 dp[i][j] =
    1. dp[i-1][j-1]+1,即s[i]==t[j]
    2. dp[i][j-1], 当s[i]!=t[j]时，s[0:i]和t[0:j]的公共子序列长度等于s[0:i]和t[0:j-1]的长度
 dp[0][0] = 0,dp[0][j] = 0, dp[i][0] = 0
 */
public class IsSubsequence {
    public boolean isSubsequence1(String s, String t) {
        int ps=0,pt=0;
        while (ps<s.length() && pt <t.length()){
            if (s.charAt(ps) == t.charAt(pt)) ps++;
            pt++;
        }
        return ps == s.length();
    }
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i-1)==t.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = dp[i][j-1];
            }
        }
        return dp[len1][len2] == len1;
    }
    public static void main(String[] args) {
        IsSubsequence Main = new IsSubsequence();
        System.out.println(Main.isSubsequence("ace", "abcde"));
    }
}
